<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    // 递归的动态规划算法--自顶向下
    function longestCommonSubsequence(text1, text2) {
      let memo = new Array(text1.length).fill(0).map(() => new Array(text2.length).fill(-1));
      // 计算 s1[0..] 和 s2[0..] 的 lcs 长度
      return dp(text1, 0, text2, 0)

      // 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
      function dp(s1, i, s2, j) {
        if (i === s1.length || j === s2.length) {
          return 0
        }

        if (memo[i][j] !== -1) {
          return memo[i][j]
        }
        if (s1[i] === s2[j]) {
          memo[i][j] = 1 + dp(s1, i + 1, s2, j + 1)
        } else {
          memo[i][j] = Math.max(dp(s1, i + 1, s2, j), dp(s1, i, s2, j + 1))
        }

        return memo[i][j]
      }
    }

    // 数组的动态规划算法--自底向上
    function longestCommonSubsequence(text1, text2) {
      let m = text1.length, n = text2.length;
      // dp数组定义：s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列长度
      let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

      // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
      // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
      // base case: dp[0][..] = dp[..][0] = 0
      for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
          // 现在 i 和 j 从 1 开始，所以要减一
          if (text1[i - 1] === text2[j - 1]) {
            // s1[i-1] 和 s2[j-1] 必然在 lcs 中，所以长度加 1
            dp[i][j] = 1 + dp[i - 1][j - 1]
          } else {
            // s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中，所以取两个值的最大值
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
          }
        }
      }

      return dp[m][n]
    }
  </script>
</body>

</html>